package com.xjc.study.operatingexamination.od.computertest;

import java.util.Scanner;

/**
 * @Description:
 * @author xujiucheng
 * 题目描述：
 * 小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。
 * 当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。
 * 小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。
 *
 * 输入描述
 * 抓取的糖果数（<10000000000）：15
 * 输出描述
 * 最少分至一颗糖果的次数：5
 * 例如
 * 输入：15  输出：5
 * 1、15+1=16
 * 2、16/2=8
 * 3、8/2=4
 * 4、4/2=2
 * 5、2/2=1
 *
 * 题目分析
 * 本题由于是每次折半，因此本题数量级即便很大，也不怕超时。
 * 没有了超时的后顾之忧，本题，直接可以暴力逻辑求解，假设输入的是num，分配次数count初始为0，那么：
 * 如果num % 2 == 0，则可以直接折半，此时分配次数count++， num /= 2
 * 如果num % 2 !=0，则不可以直接折半，此时需要开两个分支：
 * 1、取出一个糖，即num += 1，然后分配次数count++，之后继续前面折半逻辑
 * 2、放回一个糖，即num -= 1，然后分配次数count++，之后继续前面折半逻辑
 * 最终只需要在众多分支中，取最少的count即可。
 *
 */
public class ShareCandy {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLong()));
  }
 
  public static long getResult(long num) {
    int[] ans = {Integer.MAX_VALUE};
    recursive(num, 0, ans);
    return ans[0];
  }
 
  public static void recursive(long num, int count, int[] ans) {
    if (num == 1) {
      ans[0] = Math.min(ans[0], count);
      return;
    }
 
    if (num % 2 == 0) {
      recursive(num / 2, count + 1, ans);
    } else {
      recursive(num + 1, count + 1, ans);
      recursive(num - 1, count + 1, ans);
    }
  }
}